﻿#pragma once

template<class K>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{
	}
};

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree()
		:_root(0)
	{
	}

	BSTree(const BSTree<K>& t)
	{
		_root = _Copy(t._root);
	}

	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return *this;
	}

	void InOrder()
	{
		_InOrderR(_root);
		cout << endl;
	}

	bool Insert(const K& key)
	{
		return _InsertR(_root, key);
	}

	bool Find(const K& key)
	{
		return _FindR(_root, key);
	}

	bool Erase(const K& key)
	{
		return _EraseR(_root, key);
	}

	~BSTree()
	{
		Destroy(_root);
	}
private:
	Node* _root;

	Node* _Copy(const Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* node = new Node(root->_key);
		node->_left = _Copy(root->_left);
		node->_right = _Copy(root->_right);
		return node;
	}


	void _InOrderR(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrderR(root->_left);
		cout << root->_key << ' ';
		_InOrderR(root->_right);
	}

	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (key < root->_key)
		{
			_InsertR(root->_left, key);
		}
		else if (key > root->_key)
		{
			_InsertR(root->_right, key);
		}
		else
		{
			return false;
		}
		return true;
	}

	bool _FindR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (key < root->_key)
		{
			_FindR(root->_left, key);
		}
		else if (key > root->_key)
		{
			_FindR(root->_right, key);
		}
		else
		{
			return true;
		}

	}

	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}


		if (key < root->_key)
		{
			_EraseR(root->_left, key);
		}
		else if (key > root->_key)
		{
			_EraseR(root->_right, key);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* leftMax = root->_left;
				while (leftMax->_right)
				{
					leftMax = leftMax->_right;
				}
				swap(root->_key, leftMax->_key);
				return _EraseR(root->_left, key);
			}
			delete del;
			return true;
		}
	}


	void Destroy(Node*& root)
	{
		if (root == nullptr)
		{
			return;
		}

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}

};

